In computer or machine vision applications, an image is represented by a two-dimensional array of pixels. Each pixel typically has one gray value or 3 values representing each of the basic colors. Each value is an integer between 0 and a saturation (maximum) value, such as 255 in a typical 8-bit system.
One of the most important applications of industrial machine vision systems is accurate positioning: determining the coordinates of a given object within the field of view. Many high-precision manufacturing systems require very accurate object positioning. One way to improve accuracy is to increase the resolution of the vision system, which requires more expensive cameras and slows down the processing, since the image analysis time is usually proportional to the number of pixels in the image. The alternative approach is to use more accurate methods to calculate the fractional (sub-pixel) position of a pattern.
The cost and timing constraints mentioned above require many manufacturing systems to have accuracy much higher than the image resolution (pixel size), with a maximum allowed error only a few hundredths of a pixel.
The most widely used method of pattern matching is a normalized correlation algorithm. The normalized correlation coefficient between image pixels I.sub.i,j and pattern (template) pixels T.sub.i,j is defined as: ##EQU1##
When the pixel values of the image are proportional to the corresponding pixel values of the template, i.e. I.sub.i,j =a+b*T.sub.i,j, with constant coefficients a and b, the normalized correlation coefficient reaches a maximum value of one (1.0).
If image pixel values are statistically independent of the template values, the correlation coefficient is close to zero (0.0). Thus defined, the normalized correlation score is insensitive to contrast and uniform lighting variation. This property makes it a very robust measure of similarity between two images.
Using normalized correlation for accurate match position determination typically involves two steps:
1. Search for a given pattern in the whole or part of the image. Find approximate positions of normalized correlation score maxima; and PA0 2. Compute normalized correlation scores in a neighborhood around the approximate position of each local maximum. Fit a curve through this surface of score values, and compute the location of the maximum value on this curve.
The problem of interpolation of a smooth function from values sampled at regular grid intervals has received considerable attention in applied mathematics. Most interpolation algorithms are concerned with minimizing the error (absolute or mean square) between the interpolated and actual value at a given point (x,y).
One fairly simple and common way to find the maximum position is to approximate the function S(x,y) by a quadratic surface (paraboloid). This operation generally involves inverting a 6.times.6 matrix. The grid coordinates x and y are known beforehand, so the matrix can be inverted only once and the coefficients can be obtained by vector multiplication. After obtaining the coefficients, a simple linear transformation is required to reduce the quadratic form to a canonical one and find the position and value of the maximum.
This algorithm has been previously been implemented in commercial products developed by the assignee of this invention. It has an accuracy (maximum error in x or y direction) of about 0.05-0.1 pixel (1/20-1/10 of pixels size).